package com.bg.algorithms.sort;

/**
 * @author fassmus
 * 
 */
public class MergeSort extends AbstractSort {

	public MergeSort(boolean print) {
		super(print);
	}

	public void mergeSort(int[] input, int p, int r) {
		if (p < r) {
			int q = (int) Math.floor((p + r) / 2);
			mergeSort(input, p, q);
			mergeSort(input, q + 1, r);
			merge(input, p, q, r);
		}
	}

	private void merge(int[] input, int p, int q, int r) {
		int n1 = q - p + 1;
		int n2 = r - q;

		int[] left = new int[n1 + 1];
		for (int i = 1; i <= n1; i++) {
			left[i - 1] = input[p + i - 1];
		}
		left[n1] = Integer.MAX_VALUE;

		int[] right = new int[n2 + 1];
		for (int j = 1; j <= n2; j++) {
			right[j - 1] = input[q + j];
		}
		right[n2] = Integer.MAX_VALUE;

		int i = 0;
		int j = 0;

		for (int k = p; k <= r; k++) {
			if (left[i] <= right[j]) {
				input[k] = left[i];
				i = i + 1;
			} else {
				input[k] = right[j];
				j = j + 1;
			}
		}
	}
}
